package demo2;

import java.util.Stack;

/**
 * 补二叉树笔记*/
public class BinaryTree {
    //创建树节点
    public static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    //用于保存根节点
    //用于维护str的遍历
    public int i;

    public BinaryTree() {
        this.i = 0;
    }

    /**
     * 前序遍历创建二叉树
     */
    public TreeNode preCreateTree(String str) {
        if (str == null || str.charAt(i) == '#') {
            i++;
            return null;
        }
        TreeNode node = new TreeNode(str.charAt(i));
        i++;
        node.left = preCreateTree(str);
        node.right = preCreateTree(str);
        return node;
    }

    /**
     * 后序遍历二叉树（迭代实习）*/
    public void postTraversalIteration(TreeNode root) {
        if(root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur!=null || !stack.isEmpty()) {
            while(cur!=null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if(top.right == null || top.right == prev) {
                System.out.print(top.val+" ");
                prev = (stack.pop());
            } else {
                cur = top.right;
            }
        }
    }

    /**
     * 后续遍历（递归实现）*/
    public void postTraversal(TreeNode root) {
        if(root == null) {
            return;
        }
        postTraversal(root.left);
        postTraversal(root.right);
        System.out.print(root.val+" ");
    }

    /**
     * OJ 判断两棵树是否相同*/
    public boolean isSameTree(TreeNode p, TreeNode q) {
        /**
         先遍历数组*/
        if(p==null && q!=null) {
            return false;
        }
        if(p!=null && q==null) {
            return false;
        }
        if(p==null && q==null) {
            return true;
        }
        if(p.val!=q.val) {
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}